package 力扣日常刷题.木22二月.第12天218;

import 力扣日常刷题.TreeNode;

/**
 * @author 帅小伙
 * @date 2022/2/18
 * @description
 * 同
 */
public class Demo90二叉树中的最大路径和 {

    int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    public int maxGain(TreeNode node) {
        if (node == null) return 0;
        int leftGain = Math.max(0,maxGain(node.left));
        int rightGain = Math.max(0,maxGain(node.right));
        int priceNewPath = node.val + leftGain + rightGain;
        maxSum = Math.max(maxSum,priceNewPath);
        return node.val + Math.max(leftGain,rightGain);
    }

}
